// 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
// 思路1，递归，先序遍历
function pathSum(root, targetSum) {
    if (!root) {
        return []
    }
    let result = []
    let path = [root.val] // 存放路径
    function dfs(root, count) {
        count -= root.val
        if (!root.left && !root.right && count === 0) {
            result.push([...path])
            return
        }
        if (root.left) {
            path.push(root.left.val)
            dfs(root.left, count)
            path.pop()
        }
        if (root.right) {
            path.push(root.right.val)
            dfs(root.right, count)
            path.pop()
        }
    }
    dfs(root, targetSum)
    return result
}

// 思路2，遍历，前序遍历
function pathSum(root, targetSum) {
    if (!root) {
        return []
    }
    let result = []
    let stack = [root]
    let valStack = [0]
    let pathStack = [[]]
    while (stack.length) {
        let node = stack.pop()
        let curVal = valStack.pop()
        let path = pathStack.pop()
        curVal += node.val
        path.push(node.val)
        if (!node.left && !node.right && curVal === targetSum) {
            result.push([...path])
        }
        if (node.right) {
            stack.push(node.right)
            valStack.push(curVal)
            pathStack.push([...path])
        }
        if (node.left) {
            stack.push(node.left)
            valStack.push(curVal)
            pathStack.push([...path])
        }
    }
    return result
}